package com.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    String word = null;

    public TrieNode() {
    }
}

public class Leetcode212 {

    ArrayList<String> _result = new ArrayList<String>();

    public List<String> findWords(char[][] board, String[] words) {

        //1）构建Trie
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode curr = root;
            for (int i = 0; i < word.length(); i++) {
                Character ch = word.charAt(i);
                if (curr.children.containsKey(ch)) {
                    curr = curr.children.get(ch);
                } else {
                    TrieNode newNode = new TrieNode();
                    curr.children.put(ch, newNode);
                    curr = newNode;
                }
            }
            curr.word = word;
        }

        // 2） 回溯,starting for each cell in the board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (root.children.containsKey(board[i][j])) {
                    backtracking(board, i, j, root);
                }
            }
        }

        return this._result;
    }

    private void backtracking(char[][] board, int row, int col, TrieNode parent) {
        Character letter = board[row][col];
        TrieNode curr = parent.children.get(letter);

        if (curr.word != null) {
            this._result.add(curr.word);
            curr.word = null;
        }

        //设置标志位，表示该数字不可重复
        board[row][col] = '#';

        //上下左右
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : directions) {
            int newi = row + dir[0];
            int newj = col + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (curr.children.containsKey(board[newi][newj])) {
                    backtracking(board, newi, newj, curr);
                }
            }
        }

        //还原标志位
        board[row][col] = letter;

        //有结果已经保存到_result，可以将叶子节点删除，达到剪枝的效果
        if (curr.children.isEmpty()) {
            parent.children.remove(letter);
        }
    }

    public static void main(String[] args) {
        Leetcode212 leetcode212 = new Leetcode212();
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String[] word = {"SEE", "ABS"};

        System.out.println(leetcode212.findWords(board, word));
    }
}
